package com.iweb.day03;

/**
 * @author WuYongheng
 * @date 2021/10/19
 * @description 插入算法实例
 * 适用于升序排列的集合
 */
public class InsertDeom {
    public static void main(String[] args) {
        // 原成绩数组
        int [] scores = {55,60,78,90};
        // 待插入的成绩
        int newScore = 40;
        // 新数组
        int [] newScores = new int[scores.length+1];
        // 保存待插入成绩的位置
        int index = newScores.length-1;

        // 1、将原数组的元素，拷贝到新数组中
        for (int i = 0; i < scores.length; i++) {
            newScores[i] = scores[i];
        }
        // 2. 通过比较，找到待插入的成绩在新数组的位置
        for (int i = 0; i < newScores.length; i++) {
            if(newScores[i]>newScore){
                //如果当前第i个元素的值，比待插入的值要大
                // 就是要找的位置
                index=i;
                break;
            }

        }
        if (index!=newScores.length-1){
            //将该位置后的元素往后移一个位置（倒序）
            for (int j = newScores.length-1; j >index ; j--) {
                newScores[j]= newScores[j-1];
            }
        }

        // 最后，新的成绩，插入到该位置
        newScores[index]=newScore;

        // 打印验证结果
        for (int i = 0; i < newScores.length; i++) {
            System.out.print(newScores[i]+" ");
        }
    }
}
